import java.util.Arrays;


public class ShellSort {
    public static void main(String[] args) {
        //int[] arr={8,9,1,7,2,3,5,4,6,0};

        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        //System.out.println(Arrays.toString(shellSort(arr)));
        long start = System.currentTimeMillis();
        shellSort(arr);
        //
        long end = System.currentTimeMillis();
        //System.out.println(end - start);  //8097  ,交换法80000个随机数据的数组需要的ms数
        System.out.println(end - start);  //34  ,移位法80000个随机数据的数组需要的ms数
    }



    //交换法,将后面的元素对,使用冒泡排序
    public static int[] shellSortByBubble(int arr[]) {
        int temp=0;
        //gap是分组数量也是数据步长
        for (int gap=arr.length/2 ; gap>0 ;gap /= 2){
            for (int i = gap; i < arr.length; i++) {
                for (int j=i-gap;j>=0;j-=gap){
                    //找到第i个元素的前5个元素进行一次冒泡排序
                    if (arr[j]>arr[j+gap]){
                        temp=arr[j];
                        arr[j]=arr[j+gap];
                        arr[j+gap]=temp;
                    }
                }
            }
        }
        //第二轮排序
        //2组步长为2,==>从第3个数据开始依次比较3-2个数....3-2n个数的大小
        //for (int i = 2; i < arr.length; i++) {
        //    for (int j=i-2;j>=0;j-=2){
        //        //找到第i个元素的前5个元素
        //        if (arr[j]>arr[j+2]){
        //            temp=arr[j];
        //            arr[j]=arr[j+2];
        //            arr[j+2]=temp;
        //        }
        //    }
        //}
        return arr;
    }

    public static int[] shellSort(int[] arr){
        int temp=0;   // 中间变量,存放最小值
        int minIndex=0; // 最小值索引下标
        //gap是分组数量也是数据步长
        for (int gap=arr.length/2 ; gap>0 ;gap /= 2){
            for (int i = gap; i < arr.length; i++) {
                minIndex=i;
                temp=arr[minIndex];
                if (arr[minIndex]<arr[minIndex-gap]){
                    //如果minIndex-gap>=0则说明前面还有数据可以进行比较
                    while (minIndex-gap>=0 && temp<arr[minIndex-gap]){
                        arr[minIndex] =arr [minIndex-gap];
                        minIndex -=gap;
                    }
                    arr[minIndex] =temp;
                }
            }
        }
        return arr;
    }
}
